package com.datastructure.test.recall.maxlengthofascendchildserial;

public class MaxLengthOfAscendChildSerial {
    private int sum = 0;
    public static void main(String[] args) {
        int[] arr = {6,3,1,5,2,3,7};
        MaxLengthOfAscendChildSerial maxLengthOfAscendChildSerial = new MaxLengthOfAscendChildSerial();
        System.out.println(maxLengthOfAscendChildSerial.LIS(arr));
    }

    public int LIS (int[] arr) {
        // write code here
        int[][] res = new int[arr.length][arr.length];
        for(int i = 0;i< arr.length;i++){
            for(int j =0;j<arr.length;j++){
                if(i==0&&j==0){
                   continue;
                }
                if(i==0){
                    res[i][j]=res[i][j]>res[i][j-1]?res[i][j-1]+1:res[i][j];
                    continue;
                }
                if(j==0){
                    res[i][j]=res[i][j]>res[i-1][j]?res[i-1][j]+1:res[i][j];
                    continue;
                }
                dfs(arr,i,j,res);
            }
        }
        return res[arr.length-1][arr.length-1];
    }

    private void dfs(int[] arr, int i, int j,int[][] res) {
        if(arr[i]>arr[j]){
            res[i][j]=Math.max(res[i-1][j],res[i][j-1])+1;
        } else {
            res[i][j]=Math.max(res[i-1][j],res[i][j-1]);
        }
        if(i+1< arr.length){
            dfs(arr,i+1,j,res);
        }
        if(j+1< arr.length){
            dfs(arr,i,j+1,res);
        }
    }
}
